// https://leetcode.cn/problems/sliding-window-maximum/submissions/498004145/

// 双端队列（数组）：可以在队列的头部和尾部分别插入和删除元素
// 1.遍历所有数据
// 2.将数据push进双端队列，当后面的数据比前面的数据大时，将前面的的数据从队列的尾部取出，保证队列的头部永远是最大的值
// 3.有一种情况是，前面push进了一个比较大的数，然后后面push进去的数据都比它小，这个时候按照上面的条件是不能将其从队列中删除的，
    // 因为要根据索引去判断其值是否是在滑动窗口的范围内,所以push进双端队列的是其对应的索引
// 4.所以要加一个判断，当当前的索引减去滑动窗口的值小于队列头部的索引时候，将头部的数据删除

// 

function maxSlidingWindow(nums: number[], k: number): number[] {
    const n = nums.length;
    // 定义双端队列
    const deque:number[] = [];
    const res:number[] = [];    

    for(let i = 0; i < n; i++) {
        // deque[deque.length - 1]取到大时队列最后一个是索引
        while(deque.length && nums[i] > nums[deque[deque.length - 1]]){
            deque.pop()
        }
        deque.push(i);
        // 如果其超出了滚动窗口的范围，则将其从头部取出
        if(i - deque[0] >= k){
            // 从队列的头部删除数据
            deque.shift()
        }
        // 如果还没全部进入滑动窗口的范围，先不返回结果，不然会有多余的数据
        if(i >= k - 1){
            const max = nums[deque[0]];
            res.push(max)
        }
    }

    return res;
};

console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7],3))


export {}



